\appsection{Proofs}
\label{appendix:proofs}

This appendix contains proofs to the lemma and theorem in
Section~\ref{sec:opt}.


\noindent\textbf{Lemma~\ref{lemm:h-x}.} {\em Given a partial
assignment $\psi$, for each fact variable $x_{f,t} \in V(0 \leq t \leq
N)$ such that $\mu^p(x_{f,t})$ is bounded, $\mu^p(x_{f,t}) \geq
h(x_{f,t})$.}

\begin{proof}
%For each variable $x|_{v_{\psi}(x)=0}$, $\mu^p(x)=h(x)=\infty.$
We prove this lemma by mathematical induction.

%\begin{itemize}
\textbf{Basis}. When $t=0$, for each fact variable $x_{f,0}$, we
have
\[\mu^p(x_{f,0}) = \left \{
\begin{array}{cl}
0, & \mbox{$f\in I$}\\
\infty, & \mbox{$f \notin I$}\\
\end{array} \right.\]
Thus, for bounded $\mu^p(x_{f,0})$, $\mu^p(x_{f,0}) =0 =
h(x_{f,0})$. The lemma is satisfied.

\textbf{Induction}. Suppose that $\mu^p(x_{f,t}) \geq h(x_{f,t})$
for all bounded $\mu^p(x_{f,t})$ when $t \leq k$, we will prove
c$^p(x_{f,k+1})~\geq h(x_{f,k+1})$, for any $x_{f,k+1}\in V$ with
bounded $\mu^p(x_{f,k+1})$.

For each action variable $x_{o,k}$ with bounded $\mu^p(x_{o,k})$, to
make $x_{o,k}$ true, all fact variables $\{x_{f,k}|f\in pre(o)\}$
have to be true and each $\mu^p(x_{f,k})$ must also be bounded. We
thus have
\begin{align*}
\mu^p(x_{o,k}) %&~=~\mu(x_{o,k})\alpha(x_{o,k})~+~\sum\limits_{\forall{f}\in{pre(o)}}\mu^p(x_{f,k})~-~C_A\\
            &~\geq ~\mu(x_{o,k})\alpha(x_{o,k})~+~\max\limits_{{f}\in{pre(o)}}\mu^p(x_{f,k})\\
            &~\geq ~\mu(x_{o,k})\alpha(x_{o,k})~+~\max\limits_{{f}\in{pre(o)}}h(x_{f,k})\\
\end{align*}
%CRA is the cost of recomputed actions in these pathes from initial
%state to variables $\{x_{f,k}|f\in pre(o)\}$.
%and $\alpha(x)$ is the same as in Definition~\ref{def:h-action} .

We use maximum instead of summation over all precondition variables
since there may be some common action variables counted more than
once in different $\mu^p(x_{f,k})$ for different precondition
variables $x_{f,k}$. But in the special case when $\{x_{f,k}|f\in
pre(o)\}$ is an additive set, we have
\begin{align*}
\mu^p(x_{o,k})&~ =~\mu(x_{o,k})\alpha(x_{o,k})~+~\sum\limits_{{f}\in{pre(o)}}\mu^p(x_{f,k})\\
            &~\geq ~\mu(x_{o,k})\alpha(x_{o,k})~+~\sum\limits_{{f}\in{pre(o)}}h(x_{f,k})\\
\end{align*}
According to Definition~\ref{def:h-action}, we have $\mu^p(x_{o,k})
\geq h(x_{o,k})$ for any $o \in O^s$ with bounded $\mu^p(x_{o,k})$.

For each fact variable $x_{f,k+1}$  with bounded $\mu^p(x_{f,k+1})$,
to make $x_{f,k+1}$ true, at least one action variable $x_{{o,k}|f
\in add(o)}$ has to be true. Thus,
\begin{align*}
\mu^p(x_{f,k+1}) ~&~\geq \min\limits_{\{o |f\in{add(o)\}}} \mu^p(x_{o,k})\\
                &~\geq \min\limits_{\{o |f\in{add(o)\}}} h(x_{o,k})\\
                &~\geq h(x_{f,k+1}).
\end{align*}
\nop{ Since both basis and inductive step have been
proved, it has now been proved by mathematical induction that
$\mu^p(x_{f,t}) \geq h(x_{f,t})$ holds for all each variable
$x_{f,t} \in V(0 \leq t \leq N)$, which $\mu^p(x_{f,t})$ is bounded.}
\end{proof}


\noindent\textbf{Theorem~\ref{the:h-v}.} {\em Given a problem $\Pi^s=(I,F^s,O^s,G)$ transformed from a CSTE problem $\Pi=(I,F,O,G)$, and the corresponding MinCost
SAT problem $\Phi^c=(V,C,\mu)$, for any partial assignment $\psi$ of
$\Phi^c$, we have $h(\psi)\leq h^r(\psi)$.}

\begin{proof}
If there is no solution plan satisfying $\psi$, we have  $h^r(\psi) =
\infty \geq h(\psi)$. Otherwise, $h^r(\psi)$ is bounded and there exists
some bounded $\mu^p(\psi)$. \nop{ We show that, for any solution plan
reaching all goals and satisfying $\psi$, $\mu^p(\psi)\geq h(\psi)$. Because
$\mu^p(\psi)$ is bounded, all $\{\mu^p(x_{f,N})\}$ must also be
bounded. Since there might be some common action variables counted
more than once in different $\mu^p(x_{f,N})$ for different goal
variables $x_{f,N}$, suppose the cost of these action variables is
$C_A$, thus:} Consider any solution plan $p$ reaching all goals and
satisfying $\psi$, we have
\begin{align*}
\mu^p(\psi)  %&~=~\sum\limits_{\forall{f}\in{G}}\mu^p(x_{f,N})~-~C_A\\
        &~\geq ~\max\limits_{{f}\in{G}}\mu^p(x_{f,N})\\
        &~\geq ~\max\limits_{{f}\in{G}}h(x_{f,N})~(from~ Lemma~\ref{lemm:h-x})
\end{align*}
Furthermore, if the goal variables $\{x_{f,N}|f\in G\}$ form an
additive set, then we have
\begin{align*}
\mu^p(\psi)  &~=~\sum\limits_{{f}\in{G}}\mu^p(x_{f,N})\\
        &~\geq~\sum\limits_{{f}\in{G}}h(x_{f,N})~(from~Lemma~\ref{lemm:h-x})
\end{align*}
According to equation (\ref{def:h-goal}), we see that $\mu^p(\psi) \geq
h(\psi)$. Since $h^r(\psi)$ is the minimum $\mu^p(\psi)$ over all solution
plans, we have $$h^r(\psi) = \min_{p} \mu^p(\psi) \geq h(\psi).$$ Hence, the
theorem is shown.
\end{proof}
